package com.sicheng.lc.lc笔试.京东篇;

import java.util.ArrayDeque;
import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/9/3 23:01
 */
public class 括号的贡献 {
    /**
     * 题目描述
     * 定义一个括号串的权值为，它的最长合法括号子序列的长度。
     * 例如，"())())的权值是4，它的最长合法括号子序列为"()()”
     * 现在求一个给定括号串的所有子串权值之和。
     * 输入描述：
     * 一个仅包含'('和')'的字符串，长度不超过2e5。
     * 输出描述：
     * 所有子串的权值和。
     *
     *
     *
     *
     * 考虑不同子串太麻烦，可以反向考虑，考虑每一对可以匹配的括号对答案的贡献。
     * 考虑这样一个子串：xx()x，x表示任意字符。如何计算中间这对括号的贡献呢？
     * 其实可以看出来，带有这对括号的子串的数量只和它左右侧的字符数量有关，
     * 根据上面这个字符串，可以得到的带有这个括号的子串：
     *
     * xx()x
     * xx()
     * x()x
     * x()
     * ()x
     * ()
     * 也就是6个。
     * 如何得到这个数字呢？实际上就是（括号左侧的字符数+1）*（括号右侧的字符数+1）。
     * 为什么这样是正确的呢？因为我们要考虑这对括号的贡献，那么我们就要考虑所有包含该括号的子串。
     * 假设左括号左边有n个数字，那么左边其实有(n+1)种选择——什么都不选、选1个、选2个、选3个...因为要求是连续子串，
     * 所以只能有(n+1)种选择，右侧同理。两边选择的方案数需要乘起来。
     *
     * 那么只需要遍历一下字符串，查到每一个右括号对应的左括号位置，
     * (左括号左侧的字符数+1)*(右括号右侧的字符数+1)则为这个括号的贡献，
     * 总复杂度O(n)
     */

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        long res = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '(')
                stack.push(i);
            else if (!stack.isEmpty()) {
                int l = stack.pop();
                res += 2L * (l + 1) * (n - i);
            }
        }
        System.out.println(res);
    }
}
